Grover-Algorithmus

Der Grover-Algorithmus ist ein Quantenalgorithmus zur Suche in einer unsortierten Datenbank mit ${\displaystyle N}$ Einträgen in ${\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}$ Schritten und mit ${\displaystyle {\mathcal {O}}\left(\log N\right)}$ Speicherbedarf (siehe O-Notation). Er wurde von Lov Grover im Jahre 1996 veröffentlicht^[1] und gehört zu den ersten Quantenalgorithmen, für die bewiesen wurde, dass sie mit der Problemgröße besser skalieren als der beste klassische Algorithmus. Im Fall des Grover-Algorithmus handelt es sich um einen quadratischen Speedup.

Auf einem klassischen Computer ist der prinzipiell schnellstmögliche Suchalgorithmus in einer unsortierten Datenbank die lineare Suche, die ${\displaystyle {\mathcal {O}}\left(N\right)}$ Rechenschritte erfordert. Der Grover-Algorithmus liefert damit eine quadratische Beschleunigung, was für große ${\displaystyle N}$ beträchtlich ist.

Wie die meisten Quantenalgorithmen ist der Grover-Algorithmus ein probabilistischer Algorithmus, d. h., er gibt die korrekte Antwort mit hoher Wahrscheinlichkeit, wobei die Wahrscheinlichkeit einer fehlerhaften Antwort durch wiederholte Ausführung des Algorithmus verkleinert werden kann.

1. ↑ L. K. Grover: A fast quantum mechanical algorithm for database search. In: Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC). Mai 1996, S. 212–219, arxiv:quant-ph/9605043.